/**
 * 求一棵树的WLP
 * 两种方法：
 * 1.用叶子节点×路径长度
 * 2.对非叶子节点求和（这个是个结论）
 */

typedef struct node
{
    int weight;
    struct node *left;
    struct node *right;
    
}BTree;

//方法1
int func(BTree *root,int d){//d为路径长度
    if(root->left==nullptr&&root->right==nullptr){//叶子节点
        return root->weight*d;
    }else{
        return func(root->left,d+1)+func(root->right,d+1);
    }
}
int WLP(BTree *root){
    return func(root,0);
}


//方法2
//方法没问题思路也没问题，但是这些语句写的顺序看作很奇怪
int WLP2(BTree *root){
    int left,right;//左子树和右子树（不包括叶子）的权值和
    if(root->left==nullptr&&root->right==nullptr){//叶子节点
        return 0;
    }else{//非叶子节点
        //获取左子树和右子树的wlp
        left=WLP2(root->left);
        right=WLP2(root->right);
        root->weight=root->left->weight+root->right->weight;//填写非叶子节点的weight
        return (left+right+root->weight);
    }
}

